iT邦幫忙

2021 iThome 鐵人賽

DAY 28
0
自我挑戰組

Leetcode刷題筆記系列 第 28

[Day 28] Leetcode 78. Subsets (C++)

  • 分享至 

  • xImage
  •  

前言

今天來看top 100 liked的另外一medium題─78. Subsets。整個題目很單純,也沒有什麼限制,但有很多不一樣的做法可以取得答案。

想法

第一個想到的是會有幾種答案呢?答案是2^n種(n=nums.size()),因為針對nums裡面的每一個元素,都可以選擇取或不取該數,所以有2種選擇,而每一個元素都有兩種選擇,因此為2^n

recursive

而我的想法就很單純,既然每一位都可以選擇取或不取,那就用recursive的方式來對每一位去做取或不取的選擇,如下:

class Solution {
public:
    void helper(vector<vector<int>>& ans, vector<int>& nums, vector<int>& temp, int i) {
        // the last one
        if(i==nums.size()-1){
            // not choose
            ans.push_back(temp);
            // choose
            temp.push_back(nums[i]);
            ans.push_back(temp);
        }
        // not the last one
        else{
            // not choose
            helper(ans, nums, temp, i+1);
            // choose
            temp.push_back(nums[i]);
            helper(ans, nums, temp, i+1);
        }
        temp.pop_back();
    }
    
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int>> ans;
        vector<int> temp;
        int i=0;
        // for each elements, either chosen or not chosen
        helper(ans, nums, temp, i);
        return ans;
    }
};

可以注意一下我現在在function的傳遞都選擇使用傳參考的方式,因為這樣可以避免每次都要重新copy一整個vector移動來移動去,而使用這種方式要注意的就是push_back完後要pop_back,要不我在下一個recursive的時候取到的就會是已經被push_back後的值了。而我使用i代表目前檢查到那一個位數。
從討論區中可以看到各式解法,這裡有一篇整合了C++的各式解法,大略整理除了上述recursive的解法如下:

Iterative

class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int>> subs = {{}};
        for (int num : nums) {
            int n = subs.size();
            for (int i = 0; i < n; i++) {
                subs.push_back(subs[i]); 
                subs.back().push_back(num);
            }
        }
        return subs;
    }
}; 

概念
開雙層迴圈,第一層是nums的大小,第二層是目前answer set的大小;現在vector每新增一個數,我們就會變成多兩倍的組合─不選這個數就會=前面目前的全部組合,而選這個數就是把前面全部的組合都複製一次,然後加入目前這個數。每次會針對原本的再複製一次,後面加上現在的num。

Bit Manipulation

class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        int n = nums.size(), p = 1 << n;
        vector<vector<int>> subs(p);
        for (int i = 0; i < p; i++) {
            for (int j = 0; j < n; j++) {
                if ((i >> j) & 1) {
                    subs[i].push_back(nums[j]);
                }
            }
        }
        return subs;
    }
};

概念:
第一層迴圈是2^n,代表全部的組合;第二層迴圈是nums的大小,針對每一個數去對看2^n的bitset中這次要不要選取這個數。

結語

倒數第三天了,加油啊~


上一篇
[Day 27] Leetcode 207. Course Schedule (C++)
下一篇
[Day 29] Leetcode 15. 3Sum (C++)
系列文
Leetcode刷題筆記30
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言